{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Watering Plants II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumRefill"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #给植物浇水 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 和 Bob 打算给花园里的 <code>n</code> 株植物浇水。植物排成一行，从左到右进行标记，编号从 <code>0</code> 到 <code>n - 1</code> 。其中，第 <code>i</code> 株植物的位置是 <code>x = i</code> 。</p>\n",
    "\n",
    "<p>每一株植物都需要浇特定量的水。Alice 和 Bob 每人有一个水罐，<strong>最初是满的 </strong>。他们按下面描述的方式完成浇水：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>&nbsp;Alice 按 <strong>从左到右</strong> 的顺序给植物浇水，从植物 <code>0</code> 开始。Bob 按 <strong>从右到左</strong> 的顺序给植物浇水，从植物 <code>n - 1</code> 开始。他们 <strong>同时</strong> 给植物浇水。</li>\n",
    "\t<li>如果没有足够的水 <strong>完全</strong> 浇灌下一株植物，他 / 她会立即重新灌满浇水罐。</li>\n",
    "\t<li>不管植物需要多少水，浇水所耗费的时间都是一样的。</li>\n",
    "\t<li><strong>不能</strong> 提前重新灌满水罐。</li>\n",
    "\t<li>每株植物都可以由 Alice 或者 Bob 来浇水。</li>\n",
    "\t<li>如果 Alice 和 Bob 到达同一株植物，那么当前水罐中水更多的人会给这株植物浇水。如果他俩水量相同，那么 Alice 会给这株植物浇水。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>plants</code> ，数组由 <code>n</code> 个整数组成。其中，<code>plants[i]</code> 为第 <code>i</code> 株植物需要的水量。另有两个整数 <code>capacityA</code> 和&nbsp;<code>capacityB</code> 分别表示 Alice 和 Bob 水罐的容量。返回两人浇灌所有植物过程中重新灌满水罐的 <strong>次数</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>plants = [2,2,3,3], capacityA = 5, capacityB = 5\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "- 最初，Alice 和 Bob 的水罐中各有 5 单元水。\n",
    "- Alice 给植物 0 浇水，Bob 给植物 3 浇水。\n",
    "- Alice 和 Bob 现在分别剩下 3 单元和 2 单元水。\n",
    "- Alice 有足够的水给植物 1 ，所以她直接浇水。Bob 的水不够给植物 2 ，所以他先重新装满水，再浇水。\n",
    "所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 0 + 1 + 0 = 1 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>plants = [2,2,3,3], capacityA = 3, capacityB = 4\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "- 最初，Alice 的水罐中有 3 单元水，Bob 的水罐中有 4 单元水。\n",
    "- Alice 给植物 0 浇水，Bob 给植物 3 浇水。\n",
    "- Alice 和 Bob 现在都只有 1 单元水，并分别需要给植物 1 和植物 2 浇水。\n",
    "- 由于他们的水量均不足以浇水，所以他们重新灌满水罐再进行浇水。\n",
    "所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 1 + 1 + 0 = 2 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>plants = [5], capacityA = 10, capacityB = 8\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\n",
    "- 只有一株植物\n",
    "- Alice 的水罐有 10 单元水，Bob 的水罐有 8 单元水。因此 Alice 的水罐中水更多，她会给这株植物浇水。\n",
    "所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == plants.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= plants[i] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>max(plants[i]) &lt;= capacityA, capacityB &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [watering-plants-ii](https://leetcode.cn/problems/watering-plants-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [watering-plants-ii](https://leetcode.cn/problems/watering-plants-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,2,3,3]\\n5\\n5', '[2,2,3,3]\\n3\\n4', '[5]\\n10\\n8']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        n = len(plants)\n",
    "        a_begin = 0\n",
    "        a_end = n // 2 - 1\n",
    "        b_end = n // 2 + n % 2\n",
    "        b_begin = n - 1\n",
    "        left_a = []\n",
    "        left_b = []\n",
    "        cnt_a = 0\n",
    "        cnt_b = 0\n",
    "        for i in range(a_begin, a_end + 1):\n",
    "            if i:\n",
    "                if left_a[i - 1] >= plants[i]:\n",
    "                    left = left_a[i - 1] - plants[i]\n",
    "                    left_a.append(left)\n",
    "                    continue\n",
    "                else:\n",
    "                    cnt_a += 1\n",
    "            left = capacityA - plants[i]\n",
    "            left_a.append(left)\n",
    "        #print(left_a)\n",
    "        #print(cnt_a)\n",
    "        #print(b_begin, b_end, n)\n",
    "        for i in range(b_begin, b_end - 1, -1):\n",
    "            if b_begin - i:\n",
    "                if left_b[b_begin - i - 1] >= plants[i]:\n",
    "                    left = left_b[b_begin - i - 1] - plants[i]\n",
    "                    left_b.append(left)\n",
    "                    continue\n",
    "                else:\n",
    "                    cnt_b += 1\n",
    "            left = capacityB - plants[i]\n",
    "            left_b.append(left)\n",
    "        #print(left_b)\n",
    "        #print(cnt_b)\n",
    "        #print('test',len(left_b), a_end)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if len(left_a) + len(left_b) == n:\n",
    "            return cnt_a + cnt_b\n",
    "        if left_a[a_end] >= left_b[a_end - 1]:\n",
    "            if left_a[a_end] >= plants[a_end + 1]:\n",
    "                return cnt_a + cnt_b\n",
    "            else:\n",
    "                return cnt_a + cnt_b + 1\n",
    "        else:\n",
    "            if left_b[a_end] >= plants[a_end + 1]:\n",
    "                return cnt_a + cnt_b\n",
    "            else:\n",
    "                return cnt_a + cnt_b + 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        ret = 0\n",
    "        pa = 0\n",
    "        pb = len(plants)-1\n",
    "        ca = capacityA\n",
    "        cb = capacityB\n",
    "        while pa<=pb:\n",
    "            print(ca,cb)\n",
    "            if pa==pb:\n",
    "                if max(ca,cb)>=plants[pa]:\n",
    "                    break\n",
    "                else:\n",
    "                    ret += 1\n",
    "                    break\n",
    "            else:\n",
    "                if ca<plants[pa]:\n",
    "                    ret += 1\n",
    "                    ca = capacityA\n",
    "                ca -= plants[pa]\n",
    "\n",
    "                if cb<plants[pb]:\n",
    "                    ret += 1\n",
    "                    cb = capacityB\n",
    "                cb -= plants[pb]\n",
    "\n",
    "                pa += 1\n",
    "                pb -= 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(plants)\n",
    "        a = capacityA\n",
    "        b = capacityB\n",
    "        i = 0\n",
    "        j = n - 1\n",
    "        while i <= j:\n",
    "            if i == j :\n",
    "                if a < plants[i] and b < plants[i]:\n",
    "                    ans += 1\n",
    "                break\n",
    "            if a < plants[i]:\n",
    "                a = capacityA\n",
    "                ans += 1\n",
    "            a -= plants[i]\n",
    "            i += 1\n",
    "            if b < plants[j]:\n",
    "                b = capacityB\n",
    "                ans += 1\n",
    "            b -= plants[j]\n",
    "            j -= 1\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], cA: int, cB: int) -> int:\n",
    "        n = len(plants)\n",
    "        pA,pB,res = 0,n-1,0\n",
    "        A,B = cA,cB\n",
    "        while pA < pB:\n",
    "            if A < plants[pA]:\n",
    "                res += 1;A = cA\n",
    "            A -= plants[pA]\n",
    "            if B < plants[pB]:\n",
    "                res += 1;B = cB\n",
    "            pA += 1\n",
    "            B -= plants[pB]\n",
    "            pB -= 1\n",
    "        if pA == pB and A < plants[pA] and B < plants[pA]:res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        n = len(plants)\n",
    "        a = 0\n",
    "        waterA = capacityA\n",
    "        waterB = capacityB\n",
    "        b = n-1\n",
    "        res = 0\n",
    "        while a<=b:\n",
    "            if a==b:\n",
    "                waterA = max(waterA,waterB)\n",
    "                if plants[a]>waterA:\n",
    "                    res += 1\n",
    "                break\n",
    "            if plants[a]>waterA:\n",
    "                waterA = capacityA-plants[a]\n",
    "                res+=1\n",
    "            else:\n",
    "                waterA -= plants[a]\n",
    "            a += 1\n",
    "            if plants[b]>waterB:\n",
    "                waterB = capacityB-plants[b]\n",
    "                res+=1\n",
    "            else:\n",
    "                waterB -= plants[b]\n",
    "            b -= 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        n = len(plants)\n",
    "        i, j = 0, n - 1\n",
    "        a, b = capacityA, capacityB\n",
    "        ans = 0\n",
    "        while i < j:\n",
    "            if a < plants[i]:\n",
    "                ans += 1\n",
    "                a = capacityA\n",
    "            a -= plants[i]\n",
    "            if b < plants[j]:\n",
    "                ans += 1\n",
    "                b = capacityB\n",
    "            b -= plants[j]\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        if i == j:\n",
    "            mx = max(a, b)\n",
    "            if mx < plants[i]:\n",
    "                ans += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        waterA = capacityA\n",
    "        waterB = capacityB\n",
    "        ans = 0\n",
    "        n = len(plants)\n",
    "        for i in range(len(plants) >> 1):  # 如果为奇数，中间的一次留到循环外处理\n",
    "            if plants[i] > waterA:\n",
    "                ans += 1\n",
    "                waterA = capacityA\n",
    "            if plants[-1-i] > waterB:\n",
    "                ans += 1\n",
    "                waterB = capacityB\n",
    "            waterA -= plants[i]\n",
    "            waterB -= plants[-1-i]\n",
    "        if n & 1:\n",
    "            if max(waterA, waterB) < plants[n >> 1]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        res = 0   # 灌满水罐次数\n",
    "        n = len(plants)\n",
    "        posa, posb = 0, n - 1   # 两人位置\n",
    "        vala, valb = capacityA, capacityB   # 两人剩余水量\n",
    "        # 模拟相遇前的浇水过程\n",
    "        while posa < posb:\n",
    "            if vala < plants[posa]:\n",
    "                res += 1\n",
    "                vala = capacityA - plants[posa]\n",
    "            else:\n",
    "                vala -= plants[posa]\n",
    "            posa += 1\n",
    "            if valb < plants[posb]:\n",
    "                res += 1\n",
    "                valb = capacityB - plants[posb]\n",
    "            else:\n",
    "                valb -= plants[posb]\n",
    "            posb -= 1\n",
    "        # 模拟相遇后可能的浇水过程\n",
    "        if posa == posb:\n",
    "            if vala >= valb and vala < plants[posa]:\n",
    "                res += 1\n",
    "            elif vala < valb and valb < plants[posb]:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        n = len(plants)\n",
    "        a,b = 0,n-1\n",
    "        waterA,waterB = capacityA,capacityB\n",
    "        total = 0\n",
    "        while a<=b:\n",
    "            if a<b:\n",
    "                if waterA>=plants[a]:\n",
    "                    waterA -= plants[a]\n",
    "                else:\n",
    "                    total += 1\n",
    "                    waterA = capacityA-plants[a]\n",
    "                if waterB>=plants[b]:\n",
    "                    waterB -= plants[b]\n",
    "                else:\n",
    "                    total += 1\n",
    "                    waterB = capacityB-plants[b]\n",
    "            else:\n",
    "                #特殊处理两人共同浇一株植物\n",
    "                if max(waterA,waterB)<plants[a]:\n",
    "                    total += 1\n",
    "            a += 1\n",
    "            b -= 1\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        ans = 0\n",
    "        nowA, nowB = capacityA, capacityB\n",
    "        i, j = 0, len(plants) - 1\n",
    "        while i <= j:\n",
    "            if i != j:\n",
    "                if plants[i] <= nowA:\n",
    "                    nowA -= plants[i]\n",
    "                else:\n",
    "                    nowA = capacityA - plants[i]\n",
    "                    ans += 1\n",
    "                if plants[j] <= nowB:\n",
    "                    nowB -= plants[j]\n",
    "                else:\n",
    "                    nowB = capacityB - plants[j]\n",
    "                    ans += 1\n",
    "            else:\n",
    "                if nowA >= nowB:\n",
    "                    if plants[i] <= nowA:\n",
    "                        nowA -= plants[i]\n",
    "                    else:\n",
    "                        nowA = capacityA - plants[i]\n",
    "                        ans += 1\n",
    "                else:\n",
    "                    if plants[j] <= nowB:\n",
    "                        nowB -= plants[j]\n",
    "                    else:\n",
    "                        nowB = capacityB - plants[j]\n",
    "                        ans += 1\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        signA,signB=0,len(plants)-1\n",
    "        fill_A,fill_B=capacityA,capacityB\n",
    "        num=0\n",
    "        while signA<=signB:\n",
    "            if not signA==signB:\n",
    "                if plants[signA]<=capacityA:\n",
    "                    capacityA=capacityA-plants[signA]\n",
    "                else:\n",
    "                    capacityA=fill_A-plants[signA]\n",
    "                    num+=1\n",
    "                signA+=1\n",
    "                if plants[signB]<=capacityB:\n",
    "                    capacityB=capacityB-plants[signB]\n",
    "                    \n",
    "                else:\n",
    "                    capacityB=fill_B-plants[signB]\n",
    "                    num+=1\n",
    "                signB-=1\n",
    "            else:\n",
    "                if capacityA<plants[signA] and capacityB<plants[signB]:\n",
    "                    num+=1\n",
    "                break\n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        result = 0\n",
    "        capacityA_max = capacityA\n",
    "        capacityB_max = capacityB\n",
    "        p1 = 0\n",
    "        p2 = len(plants) - 1\n",
    "        while p1 <= p2:\n",
    "            if p1 == p2:\n",
    "                if max(capacityA, capacityB) < plants[p1]:\n",
    "                    result += 1\n",
    "                p1 += 1\n",
    "            else:\n",
    "                if capacityA < plants[p1]:\n",
    "                    capacityA = capacityA_max - plants[p1]\n",
    "                    result += 1\n",
    "                else:\n",
    "                    capacityA -= plants[p1]\n",
    "                if capacityB < plants[p2]:\n",
    "                    capacityB = capacityB_max - plants[p2]\n",
    "                    result += 1\n",
    "                else:\n",
    "                    capacityB -= plants[p2]\n",
    "                p1 += 1\n",
    "                p2 -= 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        a_i = capacityA\n",
    "        b_i = capacityB\n",
    "        try_number = 0\n",
    "        len_plants = len(plants)\n",
    "        for i in range(len_plants):\n",
    "            if i < len_plants-i-1:\n",
    "                if a_i<plants[i]:\n",
    "                    try_number =try_number+1\n",
    "                    a_i = capacityA\n",
    "                a_i = a_i-plants[i]\n",
    "                if b_i<plants[len_plants-i-1]:\n",
    "                    try_number =try_number+1\n",
    "                    b_i = capacityB\n",
    "                b_i = b_i-plants[len_plants-i-1]\n",
    "            if i == len_plants-i-1:\n",
    "                if a_i >= b_i:\n",
    "                    if a_i < plants[i]:\n",
    "                        try_number = try_number + 1\n",
    "                        a_i = capacityA\n",
    "                    a_i = a_i - plants[i]\n",
    "                else:\n",
    "                    if b_i < plants[i]:\n",
    "                        try_number = try_number + 1\n",
    "                        b_i = capacityB\n",
    "                    b_i = b_i - plants[i]\n",
    "            if i > len_plants-i-1:\n",
    "                break\n",
    "        return try_number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        n = len(plants)\n",
    "        ans = 0\n",
    "        capA = capacityA\n",
    "        capB = capacityB\n",
    "\n",
    "        indexA = 0\n",
    "        indexB = n - 1\n",
    "\n",
    "        while indexA < indexB:\n",
    "            if plants[indexA] > capA:\n",
    "                capA = capacityA - plants[indexA]\n",
    "                ans += 1\n",
    "            else:\n",
    "                capA -= plants[indexA]\n",
    "            indexA += 1\n",
    "\n",
    "            if plants[indexB] > capB:\n",
    "                capB = capacityB - plants[indexB]\n",
    "                ans += 1\n",
    "            else:\n",
    "                capB -= plants[indexB]\n",
    "            indexB -= 1\n",
    "\n",
    "        if indexA == indexB:\n",
    "            if max(capA, capB) < plants[indexB]:\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        counts = 0\n",
    "        A = capacityA\n",
    "        B = capacityB\n",
    "        l = len(plants)\n",
    "        j = l-1\n",
    "        for i in range(l//2):\n",
    "            if capacityA >= plants[i]:\n",
    "                capacityA -= plants[i]\n",
    "            else:\n",
    "                capacityA = A - plants[i]\n",
    "                counts +=1\n",
    "        while j > l//2:\n",
    "            if capacityB >= plants[j]:\n",
    "                capacityB -= plants[j]\n",
    "            else:\n",
    "                capacityB = B - plants[j]\n",
    "                counts += 1\n",
    "            j -= 1\n",
    "\n",
    "        if l % 2 == 0 and capacityB < plants[l//2]:\n",
    "            counts += 1\n",
    "        if l % 2 ==1:\n",
    "            if capacityA < plants[l//2] and capacityB < plants[l//2]:\n",
    "                counts += 1\n",
    "        return counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        cnt, l, r, a, b = 0, 0, len(plants) - 1, capacityA, capacityB\n",
    "        while True:\n",
    "            if l == r:\n",
    "                return cnt + (a < plants[l] and b < plants[l])\n",
    "            elif l < r:\n",
    "                if a < plants[l]:\n",
    "                    a = capacityA\n",
    "                    cnt += 1\n",
    "                a -= plants[l]\n",
    "                l += 1\n",
    "                if b < plants[r]:\n",
    "                    b = capacityB\n",
    "                    cnt += 1\n",
    "                b -= plants[r]\n",
    "                r -= 1         \n",
    "            else:\n",
    "                return cnt             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        n=len(plants)\n",
    "        a,b=capacityA,capacityB\n",
    "        ret=0\n",
    "        i,j=0,n-1\n",
    "        while i<=j:\n",
    "            if i==j:\n",
    "                if plants[i]>a and plants[i]>b:\n",
    "                    ret+=1\n",
    "                i+=1\n",
    "                j-=1\n",
    "            else:\n",
    "                if plants[i]>a:\n",
    "                    #print(\"a\",a)\n",
    "                    a=capacityA-plants[i]\n",
    "                    #print(\"i\",i,a)\n",
    "                    ret+=1\n",
    "                else:\n",
    "                    a-=plants[i]\n",
    "                if plants[j]>b:\n",
    "                    #print(\"b\",b)\n",
    "                    b=capacityB-plants[j]\n",
    "                    #print(\"j\",j,b)\n",
    "                    ret+=1\n",
    "                else:\n",
    "                    b-=plants[j] \n",
    "                i+=1\n",
    "                j-=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        waterA = capacityA\n",
    "        waterB = capacityB\n",
    "        ans = 0\n",
    "        n = len(plants)\n",
    "        for i in range(len(plants) >> 1):  # 如果为奇数，中间的一次留到循环外处理\n",
    "            if plants[i] > waterA:\n",
    "                ans += 1\n",
    "                waterA = capacityA\n",
    "            if plants[-1-i] > waterB:\n",
    "                ans += 1\n",
    "                waterB = capacityB\n",
    "            waterA -= plants[i]\n",
    "            waterB -= plants[-1-i]\n",
    "        if n & 1:\n",
    "            if max(waterA, waterB) < plants[n >> 1]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minimumRefill(self, plants, capacityA, capacityB):\n",
    "        cnt, l, r, a, b = 0, 0, len(plants) - 1, capacityA, capacityB\n",
    "        while True:\n",
    "            if l == r:\n",
    "                return cnt + (a < plants[l] and b < plants[l])\n",
    "            elif l < r:\n",
    "                if a < plants[l]:\n",
    "                    a = capacityA\n",
    "                    cnt += 1\n",
    "                a -= plants[l]\n",
    "                l += 1\n",
    "                if b < plants[r]:\n",
    "                    b = capacityB\n",
    "                    cnt += 1\n",
    "                b -= plants[r]\n",
    "                r -= 1         \n",
    "            else:\n",
    "                return cnt         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        a = 0\n",
    "        b = len(plants) - 1\n",
    "        wa = capacityA\n",
    "        wb = capacityB\n",
    "\n",
    "        times = 0\n",
    "        while a <= b:\n",
    "            if a != b:\n",
    "                if wa >= plants[a]:\n",
    "                    wa -= plants[a]\n",
    "                    a += 1\n",
    "                else:\n",
    "                    times += 1\n",
    "                    wa = capacityA - plants[a]\n",
    "                    a += 1\n",
    "                if wb >= plants[b]:\n",
    "                    wb -= plants[b]\n",
    "                    b -= 1\n",
    "                else:\n",
    "                    times += 1\n",
    "                    wb = capacityB - plants[b]\n",
    "                    b -= 1\n",
    "            elif a == b:\n",
    "                if max(wa, wb) < plants[a]:\n",
    "                    times += 1\n",
    "                break\n",
    "            #print(a,b)\n",
    "        return times\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        ans = 0 \n",
    "        n = len(plants)\n",
    "        l, r = 0, n-1\n",
    "        ca = capacityA\n",
    "        cb = capacityB \n",
    "        while l < r:\n",
    "            if ca >= plants[l]:\n",
    "                ca -= plants[l]\n",
    "            else:\n",
    "                ans += 1\n",
    "                ca = capacityA - plants[l]\n",
    "            if cb >= plants[r]:\n",
    "                cb -= plants[r]\n",
    "            else:\n",
    "                ans += 1\n",
    "                cb = capacityB - plants[r]\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        if l == r:\n",
    "            if ca >= cb:\n",
    "                ca -= plants[l]\n",
    "                if ca < 0:\n",
    "                    ans+=1\n",
    "            else:\n",
    "                cb -= plants[l]\n",
    "                if cb < 0:\n",
    "                    ans += 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        tot = 0\n",
    "        n = len(plants)\n",
    "        l, r = 0, n-1\n",
    "        ca, cb = capacityA, capacityB\n",
    "        while l < r:\n",
    "            if ca >= plants[l]:\n",
    "                ca -= plants[l]\n",
    "            else:\n",
    "                ca = capacityA - plants[l]\n",
    "                tot += 1\n",
    "            if cb >= plants[r]:\n",
    "                cb -=plants[r] \n",
    "            else:\n",
    "                cb = capacityB - plants[r] \n",
    "                tot += 1\n",
    "\n",
    "            l+=1\n",
    "            r-=1 \n",
    "        if l == r:\n",
    "            if ca >= cb and ca < plants[l]:\n",
    "                tot += 1\n",
    "            if cb > ca and cb < plants[l]:\n",
    "                tot += 1\n",
    "        return tot "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        a, b = 0, len(plants) - 1\n",
    "        A, B = capacityA, capacityB\n",
    "        res = 0\n",
    "        while a <= b:\n",
    "            if a == b:\n",
    "                if max(A, B) < plants[a]:\n",
    "                    res += 1\n",
    "            else:\n",
    "                if A < plants[a]:\n",
    "                    A = capacityA\n",
    "                    res += 1\n",
    "                if B < plants[b]:\n",
    "                    B = capacityB\n",
    "                    res += 1\n",
    "                A -= plants[a]\n",
    "                B -= plants[b]\n",
    "            a += 1\n",
    "            b -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        cnt = 0\n",
    "        leftA, leftB = capacityA, capacityB\n",
    "        n = len(plants)\n",
    "        for i in range(n // 2):\n",
    "            if leftA >= plants[i]:\n",
    "                leftA -= plants[i]\n",
    "            else:\n",
    "                leftA = capacityA - plants[i]\n",
    "                cnt += 1\n",
    "            \n",
    "            if leftB >= plants[-i-1]:\n",
    "                leftB -= plants[-i-1]\n",
    "            else:\n",
    "                leftB = capacityB - plants[-i-1]\n",
    "                cnt += 1\n",
    "        \n",
    "        if n % 2:\n",
    "            if max(leftA , leftB) < plants[n // 2]:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        n = len(plants)\n",
    "        a,b = 0,n-1\n",
    "        waterA,waterB = capacityA,capacityB\n",
    "        total = 0\n",
    "        while a<=b:\n",
    "            if a<b:\n",
    "                if waterA>=plants[a]:\n",
    "                    waterA -= plants[a]\n",
    "                else:\n",
    "                    total += 1\n",
    "                    waterA = capacityA-plants[a]\n",
    "                if waterB>=plants[b]:\n",
    "                    waterB -= plants[b]\n",
    "                else:\n",
    "                    total += 1\n",
    "                    waterB = capacityB-plants[b]\n",
    "            else:\n",
    "                #特殊处理两人共同浇一株植物\n",
    "                if max(waterA,waterB)<plants[a]:\n",
    "                    total += 1\n",
    "            a += 1\n",
    "            b -= 1\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        def func(nums, cap):\n",
    "            res = cap\n",
    "            cnt = 0\n",
    "\n",
    "            for num in nums:\n",
    "                if res >= num:\n",
    "                    res -= num\n",
    "                else:\n",
    "                    res = cap\n",
    "                    res -= num\n",
    "                    cnt += 1\n",
    "            \n",
    "            return cnt, res\n",
    "        \n",
    "        mid = len(plants) // 2\n",
    "        cnt1, res1 = func(plants[:mid], capacityA)\n",
    "        cnt2, res2 = func(plants[len(plants) - mid:][::-1], capacityB)\n",
    "\n",
    "        if len(plants) % 2 == 0:\n",
    "            return cnt1 + cnt2\n",
    "        elif max(res1, res2) >= plants[mid]:\n",
    "            return cnt1 + cnt2\n",
    "        else:\n",
    "            return cnt1 + cnt2 + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        n = len(plants)\n",
    "        a_begin = 0\n",
    "        a_end = n // 2 - 1\n",
    "        b_end = n // 2 + n % 2\n",
    "        b_begin = n - 1\n",
    "        left_a = capacityA\n",
    "        left_b = capacityB\n",
    "        cnt_a = 0\n",
    "        cnt_b = 0\n",
    "        for i in range(a_begin, a_end + 1):\n",
    "            if left_a >= plants[i]:\n",
    "                left_a -= plants[i]\n",
    "                continue\n",
    "            else:\n",
    "                cnt_a += 1\n",
    "            left_a = capacityA - plants[i]\n",
    "        print(left_a)\n",
    "        print(cnt_a)\n",
    "        print(b_begin, b_end, n)\n",
    "        for i in range(b_begin, b_end - 1, -1):\n",
    "            if left_b >= plants[i]:\n",
    "                left_b -= plants[i]\n",
    "            else:\n",
    "                cnt_b += 1\n",
    "                left_b = capacityB - plants[i]\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n % 2 == 0:\n",
    "            return cnt_a + cnt_b\n",
    "        if left_a >= left_b:\n",
    "            if left_a >= plants[a_end + 1]:\n",
    "                return cnt_a + cnt_b\n",
    "            else:\n",
    "                return cnt_a + cnt_b + 1\n",
    "        else:\n",
    "            if left_b >= plants[a_end + 1]:\n",
    "                return cnt_a + cnt_b\n",
    "            else:\n",
    "                return cnt_a + cnt_b + 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(plants)\n",
    "        A,B = capacityA,capacityB\n",
    "        l,r = 0,n-1\n",
    "        while l<n//2 and r>=n//2:\n",
    "            if plants[l]>A:\n",
    "                A = capacityA\n",
    "                ans+=1\n",
    "            A-=plants[l]\n",
    "            l+=1\n",
    "\n",
    "            if plants[r]>B:\n",
    "                B = capacityB\n",
    "                ans+=1\n",
    "            B-=plants[r]\n",
    "            r-=1\n",
    "        if n%2!=0:\n",
    "            if (A>B and plants[l]>A) or (B>A and plants[l]>B) or (B==A and plants[l]>A):\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        # 简单模拟\n",
    "        n = len(plants)\n",
    "        i = 0\n",
    "        j = n-1\n",
    "        cnt = 0\n",
    "        ca = capacityA\n",
    "        cb = capacityB\n",
    "        while i <= j:\n",
    "            if i < j:\n",
    "                if ca < plants[i]:\n",
    "                    cnt += 1\n",
    "                    ca = capacityA\n",
    "                if cb < plants[j]:\n",
    "                    cnt += 1\n",
    "                    cb = capacityB\n",
    "                ca -= plants[i]\n",
    "                cb -= plants[j]\n",
    "            else:\n",
    "                if ca >= cb:\n",
    "                    cnt += int(ca < plants[i])\n",
    "                else:\n",
    "                    cnt += int(cb < plants[j])\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return cnt\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        res = 0\n",
    "        n = len(plants)\n",
    "        posa, posb = 0, n - 1\n",
    "        vala, valb = capacityA, capacityB   # 两人剩余水量\n",
    "        # 模拟相遇前的浇水过程\n",
    "        while posa < posb:\n",
    "            if vala < plants[posa]:\n",
    "                res += 1\n",
    "                vala = capacityA - plants[posa]\n",
    "            else:\n",
    "                vala -= plants[posa]\n",
    "            posa += 1\n",
    "            if valb < plants[posb]:\n",
    "                res += 1\n",
    "                valb = capacityB - plants[posb]\n",
    "            else:\n",
    "                valb -= plants[posb]\n",
    "            posb -= 1\n",
    "        if posa == posb:\n",
    "            if vala >= valb and vala < plants[posa]:\n",
    "                res += 1\n",
    "            elif vala < valb and valb < plants[posb]:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        res = 0   # 灌满水罐次数\n",
    "        n = len(plants)\n",
    "        posa, posb = 0, n - 1   # 两人位置\n",
    "        vala, valb = capacityA, capacityB   # 两人剩余水量\n",
    "        # 模拟相遇前的浇水过程\n",
    "        while posa < posb:\n",
    "            if vala < plants[posa]:\n",
    "                res += 1\n",
    "                vala = capacityA - plants[posa]\n",
    "            else:\n",
    "                vala -= plants[posa]\n",
    "            posa += 1\n",
    "            if valb < plants[posb]:\n",
    "                res += 1\n",
    "                valb = capacityB - plants[posb]\n",
    "            else:\n",
    "                valb -= plants[posb]\n",
    "            posb -= 1\n",
    "        # 模拟相遇后可能的浇水过程\n",
    "        if posa == posb:\n",
    "            if vala >= valb and vala < plants[posa]:\n",
    "                res += 1\n",
    "            elif vala < valb and valb < plants[posb]:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        n=len(plants)\n",
    "        l=0\n",
    "        r=n-1\n",
    "        vA=capacityA\n",
    "        vB=capacityB\n",
    "        cnt=0\n",
    "        while l<r:\n",
    "            if vA>=plants[l]:\n",
    "                vA=vA-plants[l]\n",
    "            elif vA<plants[l]:\n",
    "                vA=capacityA\n",
    "                vA=vA-plants[l]\n",
    "                cnt+=1\n",
    "            if vB>=plants[r]:\n",
    "                vB=vB-plants[r]\n",
    "            elif vB<plants[r]:\n",
    "                vB=capacityB\n",
    "                vB=vB-plants[r]\n",
    "                cnt+=1\n",
    "\n",
    "            l=l+1\n",
    "            r=r-1\n",
    "            if l==r:\n",
    "                if max(vA,vB)>=plants[l]:\n",
    "                    return cnt\n",
    "                else:\n",
    "                    return cnt+1\n",
    "\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        n = len(plants)\n",
    "        i, j = 0, n - 1\n",
    "        a, b = capacityA, capacityB\n",
    "        ans = 0\n",
    "        while i < j:\n",
    "            if a < plants[i]:\n",
    "                ans += 1\n",
    "                a = capacityA - plants[i]\n",
    "            else:\n",
    "                a -= plants[i]\n",
    "            if b < plants[j]:\n",
    "                ans += 1\n",
    "                b = capacityB\n",
    "                b -= plants[j]\n",
    "            else:\n",
    "                b -= plants[j]\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        if i == j:\n",
    "            mx = max(a, b)\n",
    "            if mx < plants[i]:\n",
    "                ans += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        l,r = 0, len(plants)-1\n",
    "        ans = 0\n",
    "        ca ,cb = capacityA, capacityB\n",
    "        while l < r : \n",
    "            if ca >= plants[l] :\n",
    "                ca -= plants[l]\n",
    "            else :\n",
    "                ca = capacityA- plants[l]\n",
    "                ans += 1\n",
    "            if cb >= plants[r] :\n",
    "                cb -= plants[r]\n",
    "            else :\n",
    "                cb = capacityB- plants[r]\n",
    "                ans += 1\n",
    "            l += 1\n",
    "            r -= 1\n",
    "            #print(l,r,ca,cb,plants[l])\n",
    "            if l == r :\n",
    "                ans += int( ca < plants[l] and cb < plants[r] )    \n",
    "                return ans\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        n = len(plants)\n",
    "        half = n // 2\n",
    "        ret = 0\n",
    "        A = capacityA\n",
    "        for i in range(half):\n",
    "            if A < plants[i]:\n",
    "                A = capacityA\n",
    "                ret += 1\n",
    "            A -= plants[i]\n",
    "            \n",
    "        B = capacityB\n",
    "        for i in range(n - 1, n - half - 1, -1):\n",
    "            if B < plants[i]:\n",
    "                B = capacityB\n",
    "                ret += 1\n",
    "            B -= plants[i]\n",
    "            \n",
    "                \n",
    "        if n & 1:\n",
    "            ret += max(A, B) < plants[half]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], c1: int, c2: int) -> int:\n",
    "        i=0\n",
    "        n=len(plants)\n",
    "        j=n-1\n",
    "        m1,m2=c1,c2\n",
    "        ans=0\n",
    "        while i<j:\n",
    "           if c1>=plants[i]:\n",
    "               c1-=plants[i]\n",
    "           else:\n",
    "              \n",
    "              c1=m1-plants[i]\n",
    "              if c1>=0:\n",
    "                ans+=1\n",
    "           if c2>=plants[j]:\n",
    "               c2-=plants[j]\n",
    "           else:\n",
    "               c2=m2-plants[j]\n",
    "               if c2>=0:\n",
    "                  ans+=1\n",
    "           i+=1\n",
    "           j-=1\n",
    "        if n%2==1:\n",
    "            if max(c1,c2)<plants[n//2]:\n",
    "                ans+=1\n",
    "        return ans                            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        a = 0\n",
    "        b = len(plants)-1\n",
    "        res = 0\n",
    "        a_left = capacityA\n",
    "        b_left = capacityB\n",
    "        while a < b:\n",
    "            if a_left < plants[a]:\n",
    "                res += 1\n",
    "                a_left = capacityA - plants[a]\n",
    "            else:\n",
    "                a_left -= plants[a]\n",
    "\n",
    "            if b_left < plants[b]:\n",
    "                res += 1   \n",
    "                b_left = capacityB - plants[b]\n",
    "            else:\n",
    "                b_left -= plants[b]\n",
    "            a += 1\n",
    "            b -= 1      \n",
    "        if a == b:\n",
    "            if b_left > a_left and b_left < plants[b]:\n",
    "                res += 1\n",
    "            elif a_left >= b_left and a_left < plants[a]:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        left,right=0,len(plants)-1\n",
    "        count=0\n",
    "        A,B=capacityA,capacityB\n",
    "        while(left<=right):\n",
    "            if left==right:\n",
    "                if(A>=plants[left] or B>=plants[left]):\n",
    "                    break\n",
    "                else:\n",
    "                    count+=1\n",
    "                    break\n",
    "            if(plants[left]>A):\n",
    "                count+=1\n",
    "                A=capacityA-plants[left]\n",
    "                left+=1\n",
    "            else:\n",
    "                A=A-plants[left]\n",
    "                left+=1\n",
    "            if(plants[right]>B ):\n",
    "                count+=1\n",
    "                B=capacityB-plants[right]\n",
    "                right-=1\n",
    "            else:\n",
    "                B=B-plants[right]\n",
    "                right-=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "            left=0\n",
    "            right=len(plants)-1\n",
    "            count=0\n",
    "            left_water=capacityA\n",
    "            right_water=capacityB\n",
    "            while left<right:\n",
    "                if plants[left]<=left_water:\n",
    "                    left_water=left_water-plants[left]\n",
    "                    left+=1\n",
    "                else:\n",
    "                    count+=1\n",
    "                    left_water=capacityA-plants[left]\n",
    "                    left+=1\n",
    "                if plants[right]<=right_water:\n",
    "                    right_water=right_water-plants[right]\n",
    "                    right-=1\n",
    "                else:\n",
    "                    count+=1\n",
    "                    right_water=capacityB-plants[right]\n",
    "                    right-=1\n",
    "                if left==right:\n",
    "                    if left_water>=right_water and left_water<plants[left]:\n",
    "                        count+=1\n",
    "                        left+1\n",
    "                    if right_water>left_water and right_water<plants[right]:\n",
    "                        count+=1\n",
    "                        right-1\n",
    "            return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(plants)\n",
    "\n",
    "        def f(L, c):\n",
    "            res = 0\n",
    "            tmp = c\n",
    "            for x in L:\n",
    "                if tmp < x:\n",
    "                    res += 1\n",
    "                    tmp = c - x\n",
    "                else:\n",
    "                    tmp -= x \n",
    "            return res, tmp \n",
    "        \n",
    "        # ans += f(plants[:n // 2], capacityA)[0] + f(plants[-n // 2:][::-1], capacityB)[0]\n",
    "        cnt_a, rest_a = f(plants[:n // 2], capacityA)\n",
    "        cnt_b, rest_b = f(plants[-(n // 2):][::-1], capacityB)\n",
    "        ans += cnt_a + cnt_b\n",
    "        if n % 2 == 0:\n",
    "            return ans \n",
    "        if max(rest_a, rest_b) < plants[n // 2]:\n",
    "            ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:\n",
    "        Alice, Bob = capacityA, capacityB\n",
    "        ans = 0\n",
    "        n = len(plants)\n",
    "        left, right = 0, n - 1\n",
    "        while left <= right:\n",
    "            if left != right:\n",
    "                if Alice >= plants[left]:\n",
    "                    Alice -= plants[left]\n",
    "                else:\n",
    "                    Alice = capacityA - plants[left]\n",
    "                    ans += 1\n",
    "                left += 1\n",
    "                if Bob >= plants[right]:\n",
    "                    Bob -= plants[right]\n",
    "                else:\n",
    "                    Bob = capacityB - plants[right]\n",
    "                    ans += 1\n",
    "                right -= 1\n",
    "            else:\n",
    "                if Alice >= plants[left]:\n",
    "                    break\n",
    "                elif Bob >= plants[left]:\n",
    "                    break\n",
    "                else:\n",
    "                    ans += 1\n",
    "                    break\n",
    "        return ans\n",
    "                \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
